class Solution {
public:
    /**
     * max length of the subarray sum = k
     * @param arr int整型vector the array
     * @param k int整型 target
     * @return int整型
     */
    /*
    前缀和presum[i]=arr[0]+arr[1]+....+arr[i-1];
    presum[j]-presum[i]=arr[i]+arr[i+1]+...arr[j-1];
    哈希表中key放前缀和，value存下标
    */
    int maxlenEqualK(vector<int>& arr, int k) {
        // write code here
        if(arr.empty())
            return 0;
        unordered_map<int, int> hash;
        hash[0]=0;//哈希表初始化
        int n=arr.size();
        vector<int>presum(n+1,0); //构建前缀数组
        for(int i=1;i<=n;i++)
        {
            presum[i]=presum[i-1]+arr[i-1];
            if(hash.find(presum[i])==hash.end()) 
                //仅当presum[i]没有出现在哈希表中，才添加到哈希表中
            {
                hash[presum[i]]=i;
            }
        }
        int res=0;
        //从后往前遍历前缀和数组，其中target=presum[i]-k,tartget是在哈希表中要找的数
        for(int i=n;i>=0;i--)
        {
            int target=presum[i]-k;
            if(hash.find(target)!=hash.end())
            {
                res=max(res,i-hash[target]);
            }
        }
        return res;
    }
};